package 哈希表;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 数对和.java
 * @Description TODO
 * @createTime 2020年11月19日 10:50:00
 * 设计一个算法，找出数组中两数之和为指定值的所有整数对。一个数只能属于一个数对。
 *
 * 示例 1:
 *
 * 输入: nums = [5,6,5], target = 11
 * 输出: [[5,6]]
 * 示例 2:
 *
 * 输入: nums = [5,6,5,6], target = 11
 * 输出: [[5,6],[5,6]]
 *
 * 思路：最朴素的思路 就是哈希表记录 然后排序  排序的时候是多个if嵌套
 * 优化空间很大
 */
public class 数对和 {
    public static void main(String[] args) {
        Solution solution=new Solution();
        List<List<Integer>> lists = solution.pairSums(new int[]{5, 6, 5,6}, 11);
        System.out.println(lists.toString());
    }
    static class Solution {
        public List<List<Integer>> pairSums(int[] nums, int target) {
            HashMap<Integer,Integer>  map=new HashMap<>();
            List<List<Integer>> res=new ArrayList<>();
            for(int a:nums){
                map.put(a,map.getOrDefault(a,0)+1);
            }

            for(int i=0;i<nums.length;i++){
                if(map.get(nums[i])<1){
                    continue;
                }
                if(nums[i]==target-nums[i]){
                    if(map.get(nums[i])<2){
                        continue;
                    }
                }
               if(map.containsKey(target-nums[i])&&map.get(target-nums[i])>=1){
                   List<Integer> a=new ArrayList<>();
                   a.add(nums[i]);
                   a.add(target-nums[i]);
                   res.add(a);
                   map.put(target-nums[i],map.get(target-nums[i])-1);
                   map.put(nums[i],map.get(nums[i])-1);
               }


            }
            return res;
        }
    }
}
